\section{Algoritmos}
\label{sec:algoritmos}

A la hora de implementar los algoritmos en \ass\ decidimos utilizar la tecnolog'ia SSE version 2. Si bien versiones mas actuales proveen instrucciones que en ciertos casos hubiesen sido m'as efectivas para el procesamiento de bytes empaquetados, nos era dif'icil desarrollar en nuestras casas, donde la version SSE de los procesadores no era tan avanzada.

\subsection{Iterarando im'agenes}
\label{sec:ciclos}
La primer decisi'on a tomar a la hora de implementar los algoritmos fue como recorreremos las im'agenes. En \C\ optamos por la manera convencional, recorriendo secuencialmente la matriz, leyendo de a p'ixeles y cuando llegamos al final de cada fila salteamos el padding. Es claro que hay maneras m'as eficientes pero nos pareci'o apropiado tener esta implementaci'on como base de comparaci'on para todas las mejoras que implementaremos. 

Por otro lado, la implementaci'on en \ass\ fu'e mas ingeniosa ya que al utilizar la tecnolog'ia SSE debiamos, en principio, aprovechar al m'aximo lectura de a 16 bytes. Los problemas se presentan cuando quiero asegurarme de que estoy procesando todos los p'ixeles y que estoy evitando correctamente el \textit{padding}. En este trabajo pr'actico procesamos im'agenes a color y en escala de grises. Aunque la estrategia fue la misma, se presentaron sutiles diferencias para estos dos casos. 


\subsubsection{Im'agenes escala de grises}
En este caso cada p'ixel es representado por un byte. La iteraci'on en \C\ es bastante simple (Algoritmo \ref{alg:iteracionC-BN}). En cambio en \ass, cada vez que accedemos a memoria con un registro SSE estamos cargando 16 p'ixeles. Por lo tanto la estrategia ser'a recorrer cada fila realizando sucesivas lecturas hasta que queden menos de 16 p'ixeles para que termine la fila. Para procesar los 'ultimos datos, reposicionamos el 'indice para cargar los 'ultimos p'ixeles y volvemos a iterar. Es claro que algunos p'ixeles ser'an recalculados, pero de esta manera podemos reutilizar el c'odigo de las iteraciones normales. Cuando inicio el proceso de la nueva fila, avanzo el 'indice teniendo en cuenta el \textit{padding}. Podemos observar el pseudoc'odigo en el Algoritmo \ref{alg:iteracionASM-BN}. Cabe aclarar que los pseudoc'odigos presentados en el informe son de caracter ilustrativo, con el objetivo de explicar las estrategias utilizadas. Para un pseudoc'odigo mas detallado remitirse a los comentarios del c'odigo \ass.

\begin{algorithm}[h!]
\caption{\sc{iteraci'on en c - escala de grises}}\label{alg:iteracionC-BN}
\begin{algorithmic}[1]
\FOR{$i=0$ to $n$}
	\STATE fila $\leftarrow$ i $\times$ row\_size
	\FOR{$pos=0$ to $m$}
		\STATE dst[fila + pos] $\leftarrow$ \textit{procesar}(src[fila + pos])
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[h!]
\caption{\sc{iteraci'on en assembler - escala de grises}}\label{alg:iteracionASM-BN}
\begin{algorithmic}[1]
\FOR{$i=0$ to $n$}
	\STATE fila $\leftarrow$ i $\times$ row\_size
	\FOR{$pos=0$ to $m$}
		\STATE dst[fila + pos] $\leftarrow$ \textit{procesar_{16}}(src[fila + pos])
		\STATE pos $\leftarrow$ pos + 16		
		\IF{pos $=$ m}
			\STATE \textit{procesar\_siguiente\_fila}
		\ELSIF{pos $>$ m}		 
			\STATE pos $\leftarrow$ w - 16
		\ENDIF
		
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsubsection{Im'agenes a color}
\label{sec:ciclos-color}
En este caso cada p'ixel de las im'agenes de entrada esta representado por tres bytes(BGR). La 'unica modificacion que sufre la implementacion en \C\ es que a la hora de acceder a la matriz de entrada multiplicamos el iterador de la columna por tres. Adem'as podemos acceder a los distintos colores RGB desplazandonos cero, una o dos posiciones a partir de esa posici'on (Algoritmo \ref{alg:iteracionC-RGB}).


\begin{algorithm}[h!]
\caption{\sc{iteraci'on en c - color}}\label{alg:iteracionC-RGB}
\begin{algorithmic}[1]
\FOR{$i=0$ to $n$}
	\STATE fila_s $\leftarrow$ i $\times$ src\_row\_size	
	\STATE fila_d $\leftarrow$ i $\times$ dst\_row\_size
	\FOR{$pos=0$ to $m$}
		\STATE dst[fila_d + pos] $\leftarrow$ \textit{procesar}(src[fila_s + 3 $*$ pos])
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

En \ass (Algoritmo \ref{alg:iteracionASM-RGB}), las lecturas de a 16 bytes nos dejan en los registros 5 p'ixeles completos mas el primer byte del siguiente. Aqu'i decidimos descartar ese 'ultimo byte, procesar los datos y escribir en la imagen de salida solamente los resultados obtenidos. Es decir que mientras la imagen de entrada es recorrida de a 15 bytes(5 p'ixeles), la imagen de salida es recorrida de a 5 bytes. Por este motivo resulta imperioso llevar dos iteradores de posici'on.

Tambi'en es necesario ajustar la ultima iteraci'on de cada fila. Cuando la lectura de los 'ultimos 16 bytes, estos no quedan cargados como queremos. Para poder procesar los 'ultimos 5 p'ixeles con las mismas instrucciones que tenemos en el ciclo debemos realizar un desplazamiento a derecha de un byte (figura \ref{est:ciclo}).

\begin{figure}[h!]
\xmmW{src[15$*$i]}{\textbf{X}R_4 & G_4B_4 & R_3G_3 & B_3R_2 & G_2B_2 & R_1G_1 & B_1R_0 & G_0B_0}
\xmmW{src[3*w-16]}{R_4G_4 & B_4R_3 & G_3B_3 & R_2G_2 & B_2R_1 & G_1B_1 & R_0G_0 & B_0\textbf{R_{-1}}}
\caption{diferencia en la carga en la 'ultima iteraci'on de im'agenes a color}
\label{est:ciclo}
\end{figure}


Por otro lado, una vez que realizamos la ultima iteraci'on, debemos ajustar la condici'on de corte(linea \ref{alg:iteracionASM-RGB:corte}). Como estamos avanzando de a 15 bytes, vamos a haber finalizado la columna cuando la diferencia entre el iterador y el ancho total en bytes de la imagen de entrada sea igual a uno. Es f'acil de ver que esto solo sucede cuando se reajusta el 'indice(linea \ref{alg:iteracionASM-RGB:reajuste}), ya que no existe un caso donde falte procesar un solo byte si vengo iterando de a multiplos de 3.

\begin{algorithm}[h!]
\caption{\sc{iteraci'on en assembler - color}}\label{alg:iteracionASM-RGB}
\begin{algorithmic}[1]
\FOR{$i=0$ to $n$}
	\STATE fila_s $\leftarrow$ i $\times$ src\_row\_size	
	\STATE fila_d $\leftarrow$ i $\times$ dst\_row\_size
	\FOR{$pos=0$ to $m$}
		\STATE dato_{$16$} $\leftarrow$ src[fila + pos]
		\STATE dst[fila + pos] $\leftarrow$ \textit{procesar_{16}}(dato)
		\label{alg:iteracionASM-RGB:entry}
		\STATE pos $\leftarrow$ pos + 15		
		\IF{pos + 1 $=$ m} 		\label{alg:iteracionASM-RGB:corte}
			\STATE \textit{procesar\_siguiente\_fila}
		\ELSIF{pos $>$ m}		 
			\STATE pos $\leftarrow$ w - 16 \label{alg:iteracionASM-RGB:reajuste}
			\STATE dato_{$16$} $\leftarrow$ desplazar\_der_{1b}(src[fila + pos]) 
			\STATE \textbf{goto} linea \ref{alg:iteracionASM-RGB:entry}
		\ENDIF		
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

